<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="My Personal Website For Blog">
  <meta name="author" content="黄宇辉">
  <meta name="keywords" content="learning note,hexo blog">
  <title>详解Stack的实现方式及其应用 - 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/vs2015.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->
<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">

<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">

<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>ANONYMOUS</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                Home
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                Archives
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                Tags
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                About
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-04-13 10:00">
      April 13, 2019 am
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      3.5k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      58
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
            <article class="markdown-body">
              <h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h3 id="栈的定义-栈-Stack-是一个有序线性表-只能在表的一端-称为栈顶-top-执行插入和删除操作-最后插入的元素将第一个被删除-所以-栈也称为后进先出-Last-In-Frist-Out-LIFO-或先进后出-Fist-In-Last-Out-FILO-线性表"><a href="#栈的定义-栈-Stack-是一个有序线性表-只能在表的一端-称为栈顶-top-执行插入和删除操作-最后插入的元素将第一个被删除-所以-栈也称为后进先出-Last-In-Frist-Out-LIFO-或先进后出-Fist-In-Last-Out-FILO-线性表" class="headerlink" title="栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表."></a>栈的定义 : <code>栈(Stack)</code>是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: <code>LIFO</code>)或先进后出(Fist In Last Out: <code>FILO</code>)线性表.</h3><h3 id="注意点-两个改变栈的操作都有专用名称-一个称为入栈-psuh-表示在栈中插入一个元素-另一个称为出栈-pop-表示从栈中删除一个元素-试图对一个空栈执行出栈的操作称为下溢-underflow-试图对一个满栈执行入栈操作称为溢出-overflow-通常溢出和下溢均被认为是异常"><a href="#注意点-两个改变栈的操作都有专用名称-一个称为入栈-psuh-表示在栈中插入一个元素-另一个称为出栈-pop-表示从栈中删除一个元素-试图对一个空栈执行出栈的操作称为下溢-underflow-试图对一个满栈执行入栈操作称为溢出-overflow-通常溢出和下溢均被认为是异常" class="headerlink" title="注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop): 表示从栈中删除一个元素.试图对一个空栈执行出栈的操作称为下溢(underflow). 试图对一个满栈执行入栈操作称为溢出(overflow). 通常溢出和下溢均被认为是异常."></a>注意点 : 两个改变栈的操作都有专用名称,一个称为<code>入栈(psuh)</code>: 表示在栈中插入一个元素. 另一个称为<code>出栈(pop)</code>: 表示从栈中删除一个元素.试图对一个空栈执行出栈的操作称为<code>下溢(underflow)</code>. 试图对一个满栈执行入栈操作称为<code>溢出(overflow)</code>. 通常溢出和下溢均被认为是异常.</h3><h3 id="栈的应用"><a href="#栈的应用" class="headerlink" title="栈的应用"></a>栈的应用</h3><ul>
<li><em>直接应用</em></li>
</ul>
<ol>
<li>符号匹配.</li>
<li>中缀表达式转换为后缀表达式.</li>
<li>计算后缀表达式.</li>
<li>实现函数的调用(包括递归).</li>
<li>求范围误差(极差).</li>
<li>网页浏览器中已访问页面的历史记录(后退back按钮).</li>
<li>文本编辑器中的撤销(undo)序列.</li>
<li>HTML和XML文件中的标签(tag)匹配.</li>
</ol>
<ul>
<li><em>间接应用</em></li>
</ul>
<ol>
<li>作为一个算法的辅助数据结构(例如: 树的遍历算法).</li>
<li>其它数据结构的组件(例如: 模拟队列).</li>
</ol>
<h3 id="推荐学习方法"><a href="#推荐学习方法" class="headerlink" title="推荐学习方法"></a>推荐学习方法</h3><ul>
<li><em>推荐小伙伴们一个数据结构可视化的网站,可以大大提高学习效率哟(っ•̀ω•́)っ✎⁾⁾⁾ <a href="https://www.cs.usfca.edu/~galles/visualization/about.html" target="_blank" rel="noopener">GO !</a></em><br><img src="/2019/04/13/%E8%AF%A6%E8%A7%A3Stack%E7%9A%84%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8/ListStack.PNG" srcset="/img/loading.gif" alt=" "></li>
</ul>
<h3 id="栈的实现方式"><a href="#栈的实现方式" class="headerlink" title="栈的实现方式"></a>栈的实现方式</h3><ol>
<li>基于简单数组的实现栈 ：程序示例如下*<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: SimpleStack
 * <span class="hljs-doctag">@Description</span>: 利用简单数组实现栈
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@param</span> &lt;T&gt;
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 4:15:47 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimArrayStack</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	<span class="hljs-comment">// the size of stack</span>
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> maxSize;
	<span class="hljs-comment">// store the data</span>
	<span class="hljs-keyword">private</span> Object[] stackArray;
	<span class="hljs-comment">// the top pointer of the stack</span>
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> topPointer;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">SimArrayStack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> max)</span> </span>&#123;

		maxSize = max;
		topPointer = -<span class="hljs-number">1</span>;
		stackArray = <span class="hljs-keyword">new</span> Object[maxSize];
	&#125;

	<span class="hljs-comment">// push new data into the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">push</span><span class="hljs-params">(T element)</span> </span>&#123;
		stackArray[++topPointer] = element;
		<span class="hljs-keyword">return</span> element;
	&#125;

	<span class="hljs-comment">// peek the top data in the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> Object <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> stackArray[topPointer];
	&#125;

	<span class="hljs-comment">// determines whether the stack is empty</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> topPointer == -<span class="hljs-number">1</span>;
	&#125;

	<span class="hljs-comment">// pop the data in the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> Object <span class="hljs-title">pop</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> stackArray[topPointer--];
	&#125;

	<span class="hljs-comment">// pop all of data in the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">popAll</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (isEmpty()) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
		<span class="hljs-keyword">while</span> (!isEmpty()) &#123;
			System.out.println(<span class="hljs-string">"The element to be poped : "</span> + pop());
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// Iterate through all the data in the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverseElement</span><span class="hljs-params">()</span> </span>&#123;
		System.out.print(<span class="hljs-string">"All of element in the stack : "</span>);
		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; stackArray.length; i++) &#123;
			<span class="hljs-keyword">if</span> (i != stackArray.length - <span class="hljs-number">1</span>) &#123;
				System.out.print(stackArray[i] + <span class="hljs-string">" , "</span>);
			&#125; <span class="hljs-keyword">else</span> &#123;
				System.out.print(stackArray[i]);
			&#125;
		&#125;
		System.out.println();
	&#125;

	<span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		<span class="hljs-comment">// SimpleStack&lt;Character&gt; stack2 = new SimpleStack&lt;Character&gt;(6);</span>
		SimArrayStack&lt;Integer&gt; stack = <span class="hljs-keyword">new</span> SimArrayStack&lt;Integer&gt;(<span class="hljs-number">6</span>);
		stack.push(<span class="hljs-number">1</span>);
		stack.push(<span class="hljs-number">2</span>);
		stack.push(<span class="hljs-number">3</span>);
		stack.push(<span class="hljs-number">4</span>);
		stack.push(<span class="hljs-number">5</span>);
		stack.push(<span class="hljs-number">6</span>);

		stack.traverseElement();
		System.out.println(<span class="hljs-string">"The element to be poped : "</span> + stack.pop());
		System.out.println(<span class="hljs-string">"The top element : "</span> + stack.peek());
		System.out.println(<span class="hljs-string">"Push a new element : "</span> + stack.push(<span class="hljs-number">7</span>));
		System.out.println(<span class="hljs-string">"The top element : "</span> + stack.peek());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());
		System.out.println(<span class="hljs-string">"Pop all of elements : "</span> + stack.popAll());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());

	&#125;
&#125;

<span class="hljs-comment">/* ## The program running results are as follows :

All of element in the stack : 1 , 2 , 3 , 4 , 5 , 6
The element to be poped : 6
The top element : 5
Push a new element : 7
The top element : 7
Determines whether the stack is empty : false
The element to be poped : 7
The element to be poped : 5
The element to be poped : 4
The element to be poped : 3
The element to be poped : 2
The element to be poped : 1
Pop all of elements : true
Determines whether the stack is empty : true

 */</span></code></pre></div>
<h4 id="局限性-栈的最大空间必须预先声明且不能改变-试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常"><a href="#局限性-栈的最大空间必须预先声明且不能改变-试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常" class="headerlink" title="局限性 : 栈的最大空间必须预先声明且不能改变.试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常 !"></a>局限性 : 栈的最大空间必须预先声明且不能改变.试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常 !</h4></li>
</ol>
<ol start="2">
<li><p><em>基于动态数组的实现栈 ：程序示例如下</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: DynArrayStack
 * <span class="hljs-doctag">@Description</span>: 利用动态数组实现栈
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 11, 2019 5:49:02 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DynArrayStack</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> topPointer;
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> capacity;
	<span class="hljs-keyword">private</span> Object[] array;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">DynArrayStack</span><span class="hljs-params">()</span> </span>&#123;
		topPointer = -<span class="hljs-number">1</span>;
		capacity = <span class="hljs-number">1</span>;
		array = <span class="hljs-keyword">new</span> Object[capacity];
	&#125;

	<span class="hljs-comment">// determines whether the stack is empty</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> (topPointer == -<span class="hljs-number">1</span>);
	&#125;

	<span class="hljs-comment">// determines whether the stack is full</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isStackFull</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> (topPointer == capacity - <span class="hljs-number">1</span>);<span class="hljs-comment">// or return (topPointer==array.length);</span>
	&#125;

	<span class="hljs-comment">// peek the top data of the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> Object <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> array[topPointer];
	&#125;

	<span class="hljs-comment">// push a new data into the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">push</span><span class="hljs-params">(T element)</span> </span>&#123;
		<span class="hljs-keyword">if</span> (isStackFull()) &#123;
			doubleStack();
		&#125;
		array[++topPointer] = element;

		<span class="hljs-keyword">return</span> element;
	&#125;

	<span class="hljs-comment">// double the size of the array</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">doubleStack</span><span class="hljs-params">()</span> </span>&#123;
		Object newArr[] = <span class="hljs-keyword">new</span> Object[capacity * <span class="hljs-number">2</span>];
		System.arraycopy(array, <span class="hljs-number">0</span>, newArr, <span class="hljs-number">0</span>, capacity);
		capacity *= <span class="hljs-number">2</span>;
		array = newArr;
	&#125;

	<span class="hljs-comment">// pop the data from the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> Object <span class="hljs-title">pop</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (isEmpty()) &#123;
			System.err.println(<span class="hljs-string">"The Stack is  overflow !"</span>);
		&#125;
		<span class="hljs-keyword">return</span> array[topPointer--];
	&#125;

	<span class="hljs-comment">// pop all of data from the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">popAll</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (isEmpty()) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
		<span class="hljs-keyword">while</span> (!isEmpty()) &#123;
			System.out.println(<span class="hljs-string">"The element to be poped : "</span> + pop());
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// Iterate through all the data in the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverseElement</span><span class="hljs-params">()</span> </span>&#123;
		System.out.print(<span class="hljs-string">"all of element in the stack : "</span>);
		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; array.length; i++) &#123;
			<span class="hljs-keyword">if</span> (i != array.length - <span class="hljs-number">1</span>) &#123;
				System.out.print(array[i] + <span class="hljs-string">" , "</span>);
			&#125;
		&#125;
		System.out.println();
	&#125;

	<span class="hljs-comment">// delete the stack</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">deleteStack</span><span class="hljs-params">()</span> </span>&#123;
		topPointer = -<span class="hljs-number">1</span>;
	&#125;

    <span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		DynArrayStack&lt;Character&gt; stack = <span class="hljs-keyword">new</span> DynArrayStack&lt;Character&gt;();
		stack.push(<span class="hljs-string">'a'</span>);
		stack.push(<span class="hljs-string">'b'</span>);
		stack.push(<span class="hljs-string">'c'</span>);
		stack.push(<span class="hljs-string">'d'</span>);
		stack.push(<span class="hljs-string">'e'</span>);
		stack.push(<span class="hljs-string">'f'</span>);
		stack.push(<span class="hljs-string">'g'</span>);

		stack.traverseElement();
		System.out.println(<span class="hljs-string">"The element to be poped : "</span> + stack.pop());
		System.out.println(<span class="hljs-string">"The top element : "</span> + stack.peek());
		System.out.println(<span class="hljs-string">"Push a new element : "</span> + stack.push(<span class="hljs-string">'h'</span>));
		System.out.println(<span class="hljs-string">"The top element : "</span> + stack.peek());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());
		System.out.println(<span class="hljs-string">"Pop all of elements : "</span> + stack.popAll());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());

	&#125;
&#125;

<span class="hljs-comment">/*## The program running results are as follows :

all of element in the stack : a , b , c , d , e , f , g , 
The element to be poped : g
The top element : f
Push a new element : h
The top element : h
Determines whether the stack is empty : false
The element to be poped : h
The element to be poped : f
The element to be poped : e
The element to be poped : d
The element to be poped : c
The element to be poped : b
The element to be poped : a
Pop all of elements : true
Determines whether the stack is empty : true

 */</span></code></pre></div>
<h4 id="注意-倍增太多可能导致内存溢出"><a href="#注意-倍增太多可能导致内存溢出" class="headerlink" title="注意 : 倍增太多可能导致内存溢出 !"></a>注意 : 倍增太多可能导致<code>内存溢出</code> !</h4><h4 id="上述程序中利用重复倍增技术-提高了程序的性能-其总时间开销T-n-≈-O-n-相比采用-当栈满时-每次将数组的大小增加1更加节省了push操作的总时间开销-其总时间开销T-n-≈-O-n²"><a href="#上述程序中利用重复倍增技术-提高了程序的性能-其总时间开销T-n-≈-O-n-相比采用-当栈满时-每次将数组的大小增加1更加节省了push操作的总时间开销-其总时间开销T-n-≈-O-n²" class="headerlink" title="上述程序中利用重复倍增技术)提高了程序的性能,其总时间开销T(n) ≈ O(n) . 相比采用: 当栈满时,每次将数组的大小增加1更加节省了push操作的总时间开销.其总时间开销T(n) ≈ O(n²) ."></a>上述程序中利用<code>重复倍增技术)</code>提高了程序的性能,其总时间开销<code>T(n) ≈ O(n)</code> . 相比采用: 当栈满时,每次将数组的大小增加<code>1</code>更加节省了<code>push</code>操作的总时间开销.其总时间开销<code>T(n) ≈ O(n²)</code> .</h4></li>
<li><p><em>基于链表来实现栈 ：程序示例如下</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: ListNode
 * <span class="hljs-doctag">@Description</span>: 定义链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 11, 2019 7:01:35 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ListNode</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	<span class="hljs-keyword">private</span> T data;
	<span class="hljs-keyword">private</span> ListNode&lt;T&gt; next;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ListNode</span><span class="hljs-params">(T d)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.data = d;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">getData</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setData</span><span class="hljs-params">(T data)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.data = data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;T&gt; <span class="hljs-title">getNext</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> next;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setNext</span><span class="hljs-params">(ListNode&lt;T&gt; next)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.next = next;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"["</span> + data + <span class="hljs-string">"]"</span>;
	&#125;
&#125;</code></pre></div>

</li>
</ol>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: ListStack
 * <span class="hljs-doctag">@Description</span>: 利用链表实现栈
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 11, 2019 6:59:46 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ListStack</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;

	<span class="hljs-keyword">private</span> ListNode&lt;E&gt; headNode;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ListStack</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">this</span>.headNode = <span class="hljs-keyword">new</span> ListNode&lt;E&gt;(<span class="hljs-keyword">null</span>);
	&#125;

	<span class="hljs-comment">// push a new node into the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;E&gt; <span class="hljs-title">push</span><span class="hljs-params">(E data)</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			headNode = <span class="hljs-keyword">new</span> ListNode&lt;E&gt;(data);
		&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (headNode.getData() == <span class="hljs-keyword">null</span>) &#123;
			headNode.setData(data);<span class="hljs-comment">// initialize header node.</span>
		&#125; <span class="hljs-keyword">else</span> &#123;
			ListNode&lt;E&gt; newNode = <span class="hljs-keyword">new</span> ListNode&lt;E&gt;(data); <span class="hljs-comment">// create a new node.</span>
			newNode.setNext(headNode);<span class="hljs-comment">// connect to the header node.</span>
			headNode = newNode;<span class="hljs-comment">// set the new node to header node.</span>

		&#125;
		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// returns the top node of the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">top</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
		&#125; <span class="hljs-keyword">else</span> &#123;
			<span class="hljs-keyword">return</span> headNode.getData();
		&#125;
	&#125;

	<span class="hljs-comment">// pop top node in the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">pop</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> EmptyStackException();
		&#125; <span class="hljs-keyword">else</span> &#123;
			E node = headNode.getData();
			headNode = headNode.getNext();<span class="hljs-comment">// Reset the header node.</span>
			<span class="hljs-keyword">return</span> node;
		&#125;
	&#125;

	<span class="hljs-comment">// pop all of nodes in the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">popAll</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> EmptyStackException();
		&#125;
		<span class="hljs-keyword">while</span> (!isEmpty()) &#123;
			System.out.println(<span class="hljs-string">"Pop all of nodes : "</span> + pop());
		&#125;
		<span class="hljs-keyword">if</span> (isEmpty()) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// determine whether the linked list is empty</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
		&#125; <span class="hljs-keyword">else</span> &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
	&#125;

	<span class="hljs-comment">// Iterate through all the node in the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">getNodeByLoop</span><span class="hljs-params">(ListNode&lt;E&gt; head)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (isEmpty()) &#123;
			<span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> EmptyStackException();
		&#125;

		System.out.print(<span class="hljs-string">"All of nodes of the linked list:  "</span>);
		<span class="hljs-keyword">while</span> (head != <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">if</span> (head.getNext() != <span class="hljs-keyword">null</span>) &#123;
				System.out.print(head.getData() + <span class="hljs-string">" , "</span>);
			&#125; <span class="hljs-keyword">else</span> &#123;
				System.out.print(head.getData());
			&#125;
			head = head.getNext();
		&#125;
		System.out.println();
	&#125;

	<span class="hljs-comment">// destroy the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">destroyStack</span><span class="hljs-params">(<span class="hljs-comment">/* ListNode&lt;E&gt; head */</span>)</span> </span>&#123;

		ListNode&lt;E&gt; auxilaryNode = <span class="hljs-keyword">null</span>, iterator = headNode;
		<span class="hljs-keyword">while</span> (iterator != <span class="hljs-keyword">null</span>) &#123;
			auxilaryNode = iterator.getNext();
			iterator = <span class="hljs-keyword">null</span>;
			iterator = auxilaryNode;

			headNode = iterator;<span class="hljs-comment">// Set the node to be deleted as the header node.</span>
		&#125;
		<span class="hljs-keyword">if</span> (auxilaryNode == <span class="hljs-keyword">null</span>) &#123;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
	&#125;

	<span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		<span class="hljs-comment">// ListStack&lt;Integer&gt; stack = new ListStack&lt;Integer&gt;();</span>
		ListStack&lt;String&gt; stack = <span class="hljs-keyword">new</span> ListStack&lt;String&gt;();
		stack.push(<span class="hljs-string">"A"</span>);
		stack.push(<span class="hljs-string">"B"</span>);
		stack.push(<span class="hljs-string">"C"</span>);
		stack.push(<span class="hljs-string">"D"</span>);
		stack.push(<span class="hljs-string">"E"</span>);
		stack.push(<span class="hljs-string">"F"</span>);
		stack.push(<span class="hljs-string">"G"</span>);

		stack.getNodeByLoop(stack.headNode);
		System.out.println(<span class="hljs-string">"The node to be poped : "</span> + stack.pop());
		System.out.println(<span class="hljs-string">"The top node : "</span> + stack.top());
		System.out.println(<span class="hljs-string">"Push a new node : "</span> + stack.push(<span class="hljs-string">"H"</span>));
		System.out.println(<span class="hljs-string">"The top node : "</span> + stack.top());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());
		System.out.println(<span class="hljs-string">"Pop all of nodes(success ?) : "</span> + stack.popAll());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());
		System.out.println(<span class="hljs-string">"Push a new node : "</span> + stack.push(<span class="hljs-string">"I"</span>));
		System.out.println(<span class="hljs-string">"Push a new node : "</span> + stack.push(<span class="hljs-string">"J"</span>));
		System.out.println(<span class="hljs-string">"Push a new node : "</span> + stack.push(<span class="hljs-string">"K"</span>));
		System.out.println(<span class="hljs-string">"Destroy the stack(success ?) : "</span> + stack.destroyStack());
		System.out.println(<span class="hljs-string">"Determines whether the stack is empty : "</span> + stack.isEmpty());

	&#125;

&#125;

<span class="hljs-comment">/*## The program running results are as follows :

All of nodes of the linked list:  G , F , E , D , C , B , A
The node to be poped : G
The top node : F
Push a new node : [H]
The top node : H
Determines whether the stack is empty : false
Pop all of nodes : H
Pop all of nodes : F
Pop all of nodes : E
Pop all of nodes : D
Pop all of nodes : C
Pop all of nodes : B
Pop all of nodes : A
Pop all of nodes(success ?) : true
Determines whether the stack is empty : true
Push a new node : [I]
Push a new node : [J]
Push a new node : [K]
Destroy the stack(success ?) : true
Determines whether the stack is empty : true

 */</span></code></pre></div>

<h3 id="栈的各种实现方法的比较"><a href="#栈的各种实现方法的比较" class="headerlink" title="栈的各种实现方法的比较"></a>栈的各种实现方法的比较</h3><ol>
<li><strong>递增策略和倍增策略的比较</strong></li>
</ol>
<ul>
<li><em>通过分析完成<code>n</code>个<code>push</code>操作的总时间开销<code>T(n)</code>来比较递增策略和倍增策略的区别.从长度为<code>1</code>的数组表示的空栈开始,一次<code>push</code>操作的平摊时间等于一组<code>push</code>操作的总时间开销的平均值.记为 : <code>T(n)/n</code></em></li>
<li><em><code>递增策略</code> : 实现<code>push</code>操作的平摊时间开销为<code>O(n)[O(n²)/n]</code> .</em></li>
<li><em><code>倍增策略</code> : 实现<code>push</code>操作的平摊时间开销为<code>O(n)[O(n)/n]</code> .</em></li>
</ul>
<ol start="2">
<li><strong>基于数组实现和基于链表实现的比较</strong><h4 id="a-：基于数组实现的栈"><a href="#a-：基于数组实现的栈" class="headerlink" title="(a) ：基于数组实现的栈"></a>(a) ：基于数组实现的栈</h4></li>
</ol>
<ul>
<li><em>各个操作都是常数时间开销.</em></li>
<li><em>每隔一段时间倍增操作的开销过大.</em></li>
<li><em>(从空栈开始)<code>n</code>个操作的任意序列的平摊时间开销为<code>O(n)</code>.</em><h4 id="b-：基于链表实现的栈"><a href="#b-：基于链表实现的栈" class="headerlink" title="(b) ：基于链表实现的栈"></a>(b) ：基于链表实现的栈</h4></li>
<li><em>栈规模的增加和减少都是很简洁.</em></li>
<li><em>各个操作都是常数时间开销.</em></li>
<li><em>每个操作都要使用额外的空间和时间开销来处理指针.</em></li>
</ul>
<h3 id="栈的应用-1"><a href="#栈的应用-1" class="headerlink" title="栈的应用"></a>栈的应用</h3><ol>
<li><em>举例<code>1</code> ：将用户输入的字符反转</em></li>
</ol>
<ul>
<li><p><em>首先定义一个基于简单数组的栈</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: SimpleStack
 * <span class="hljs-doctag">@Description</span>: 栈
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 8:50:56 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimpleStack</span> </span>&#123;

	<span class="hljs-comment">// 栈的大小</span>
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> maxSize;
	<span class="hljs-comment">// 存储栈元素</span>
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">char</span>[] stackArray;
	<span class="hljs-comment">// 栈顶指针</span>
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> topPointer;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">SimpleStack</span><span class="hljs-params">(<span class="hljs-keyword">int</span> max)</span> </span>&#123;

		maxSize = max;
		topPointer = -<span class="hljs-number">1</span>;
		stackArray = <span class="hljs-keyword">new</span> <span class="hljs-keyword">char</span>[maxSize];
	&#125;

	<span class="hljs-comment">// 逐个向栈中压入元素</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">push</span><span class="hljs-params">(<span class="hljs-keyword">char</span> c)</span> </span>&#123;
		stackArray[++topPointer] = c;
	&#125;

	<span class="hljs-comment">// 逐个弹出栈中元素</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">char</span> <span class="hljs-title">pop</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> stackArray[topPointer--];
	&#125;

	<span class="hljs-comment">// 弹出栈中所有的元素</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">popAll</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">while</span> (!isEmpty()) &#123;
			System.out.println(<span class="hljs-string">"pop element : "</span> + pop());
		&#125;
	&#125;

	<span class="hljs-comment">// 查看栈顶元素</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">char</span> <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> stackArray[topPointer];
	&#125;

	<span class="hljs-comment">// 判断栈是否为空</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> topPointer == -<span class="hljs-number">1</span>;
	&#125;
&#125;</code></pre></div>
</li>
<li><p><em>利用栈来反转字符</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: MyStack
 * <span class="hljs-doctag">@Description</span>: 利用栈来反转字符串
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 3:46:40 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ReversalString</span> </span>&#123;

	<span class="hljs-keyword">private</span> String input;
	<span class="hljs-keyword">private</span> String output;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ReversalString</span><span class="hljs-params">(String in)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.input = in;
	&#125;

	<span class="hljs-comment">// 反转字符</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">doReversal</span><span class="hljs-params">()</span> </span>&#123;

		<span class="hljs-keyword">int</span> stackSize = input.length();
		SimpleStack stack = <span class="hljs-keyword">new</span> SimpleStack(stackSize);

		<span class="hljs-comment">// 将字符逐个压入栈中</span>
		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; input.length(); i++) &#123;
			<span class="hljs-keyword">char</span> in = input.charAt(i);
			stack.push(in);
		&#125;

		<span class="hljs-comment">// 将字符逐个从栈中取出</span>
		output = <span class="hljs-string">""</span>;
		<span class="hljs-keyword">while</span> (!stack.isEmpty()) &#123;
			<span class="hljs-keyword">char</span> out = stack.pop();
			output += out;
		&#125;

		<span class="hljs-keyword">return</span> output;
	&#125;
&#125;</code></pre></div>
</li>
<li><p><em>接收用户输入的字符并测试</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: ReversalStringTest
 * <span class="hljs-doctag">@Description</span>: 测试反转字符程序
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 8:53:24 PM
 * 
 */</span>

<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ReversalStringTest</span> </span>&#123;

	<span class="hljs-keyword">static</span> BufferedReader bufferedReader;

	<span class="hljs-meta">@Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">reversalTest</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> IOException </span>&#123;
		String input, output;

		<span class="hljs-keyword">while</span> (<span class="hljs-keyword">true</span>) &#123;
			System.out.println(<span class="hljs-string">"Please enter a string : "</span>);
			<span class="hljs-comment">// System.out.flush();</span>
			input = getString();
			<span class="hljs-keyword">if</span> (input.equals(<span class="hljs-string">"exit"</span>)) &#123;
				bufferedReader.close();
				<span class="hljs-keyword">break</span>;
			&#125;

			<span class="hljs-comment">// 将字符串反转</span>
			ReversalString reversal = <span class="hljs-keyword">new</span> ReversalString(input);
			output = reversal.doReversal();

			System.out.println(<span class="hljs-string">"Reversed : "</span> + output);
		&#125;
	&#125;

	<span class="hljs-meta">@Test</span>
	<span class="hljs-meta">@Ignore</span>
	<span class="hljs-comment">// 测试BufferedString中的控制字符反转的方法</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">BufferedStringTest</span><span class="hljs-params">()</span> </span>&#123;

		StringBuffer stringBuffer = <span class="hljs-keyword">new</span> StringBuffer(<span class="hljs-string">"reverse"</span>);

		System.err.println(<span class="hljs-string">"Reversed : "</span> + stringBuffer.reverse());

	&#125;

	<span class="hljs-comment">// 通过缓冲流中的'readLine'方法高效读入用户输入的数据</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">getString</span><span class="hljs-params">()</span> </span>&#123;

		String s = <span class="hljs-keyword">null</span>;
		bufferedReader = <span class="hljs-keyword">new</span> BufferedReader(<span class="hljs-keyword">new</span> InputStreamReader(System.in));
		<span class="hljs-keyword">try</span> &#123;
			s = bufferedReader.readLine();
		&#125; <span class="hljs-keyword">catch</span> (IOException e) &#123;
			e.printStackTrace();
		&#125;
		<span class="hljs-keyword">return</span> s;
	&#125;
&#125;</code></pre></div></li>
<li><p><em>程序运行结果如下 :</em></p>
<div class="hljs"><pre><code class="hljs java">Please enter a string : 
my qq: <span class="hljs-number">3083968068</span>

Reversed : <span class="hljs-number">8608693803</span> :qq ym

Please enter a string : 
exit</code></pre></div>
</li>
</ul>
<ol start="2">
<li><em>举例 ：检查用户输入的运算符(括号匹配)</em></li>
</ol>
<ul>
<li><p><em>首先定义一个基于简单数组的栈(同上,略写)</em></p>
</li>
<li><p><em>利用栈中入栈和出栈操作匹配括号符</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: BracketChecker
 * <span class="hljs-doctag">@Description</span>: 匹配括号
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 9:58:36 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BracketChecker</span> </span>&#123;

	<span class="hljs-keyword">private</span> String input;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">BracketChecker</span><span class="hljs-params">(String in)</span> </span>&#123;

		<span class="hljs-keyword">this</span>.input = in;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">chekc</span><span class="hljs-params">()</span> </span>&#123;

		<span class="hljs-keyword">boolean</span> flag_a = <span class="hljs-keyword">false</span>;
		<span class="hljs-keyword">boolean</span> flag_b = <span class="hljs-keyword">false</span>;
		<span class="hljs-keyword">int</span> stackSize = input.length();
		SimpleStack stack = <span class="hljs-keyword">new</span> SimpleStack(stackSize);

		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; input.length(); i++) &#123;
			<span class="hljs-keyword">char</span> in = input.charAt(i);

			<span class="hljs-keyword">switch</span> (in) &#123;
			<span class="hljs-keyword">case</span> <span class="hljs-string">'&#123;'</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">'('</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">'['</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">'&lt;'</span>:
				stack.push(in);
				<span class="hljs-keyword">break</span>;
			<span class="hljs-keyword">case</span> <span class="hljs-string">'&#125;'</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">')'</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">']'</span>:
			<span class="hljs-keyword">case</span> <span class="hljs-string">'&gt;'</span>:
				<span class="hljs-comment">// 括号匹配</span>
				<span class="hljs-keyword">if</span> (!stack.isEmpty()) &#123;
					<span class="hljs-keyword">char</span> out = stack.pop();
					<span class="hljs-keyword">if</span> ((in == <span class="hljs-string">'&#125;'</span> &amp;&amp; out != <span class="hljs-string">'&#123;'</span>) || (in == <span class="hljs-string">')'</span> &amp;&amp; out != <span class="hljs-string">'('</span>) || (in == <span class="hljs-string">']'</span> &amp;&amp; out != <span class="hljs-string">'['</span>)
							|| (in == <span class="hljs-string">'&gt;'</span> &amp;&amp; out != <span class="hljs-string">'&lt;'</span>)) &#123;
						System.err.println(<span class="hljs-string">"error : "</span> + in + <span class="hljs-string">" at "</span> + i);
					&#125; <span class="hljs-keyword">else</span> &#123;
						flag_a = <span class="hljs-keyword">true</span>;
					&#125;
				&#125; <span class="hljs-keyword">else</span> &#123;
					System.err.println(<span class="hljs-string">"error : "</span> + in + <span class="hljs-string">" at "</span> + i);
					flag_a = <span class="hljs-keyword">false</span>;
				&#125;

				<span class="hljs-keyword">break</span>;
			<span class="hljs-comment">// 只检查括号</span>
			<span class="hljs-keyword">default</span>:
				<span class="hljs-keyword">break</span>;
			&#125;
		&#125;

		<span class="hljs-comment">// 如果匹配成功,循环结束后栈中理应为空.</span>
		<span class="hljs-keyword">if</span> (!stack.isEmpty()) &#123;
			System.out.println(<span class="hljs-string">"Error : missing right delimiter."</span>);
		&#125; <span class="hljs-keyword">else</span> &#123;
			flag_b = <span class="hljs-keyword">true</span>;
		&#125;

		<span class="hljs-keyword">if</span> (flag_a &amp;&amp; flag_b) &#123;
			System.out.println(<span class="hljs-string">"Success !"</span>);
		&#125;
	&#125;
&#125;</code></pre></div>
</li>
<li><p><em>接收用户输入的运算符并测试匹配程序</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: BracketCheckerTest
 * <span class="hljs-doctag">@Description</span>: 测试匹配括号符程序
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 10, 2019 9:58:55 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BracketCheckerTest</span> </span>&#123;
	
	<span class="hljs-keyword">static</span> BufferedReader bufferedReader;
	
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> <span class="hljs-keyword">throws</span> IOException </span>&#123;
		
		String input;
		
		<span class="hljs-keyword">while</span>(<span class="hljs-keyword">true</span>) &#123;
			System.out.println(<span class="hljs-string">"Please enter containing delimiters : "</span>);
			System.out.flush();
			input = getString();
			<span class="hljs-keyword">if</span>(input.equals(<span class="hljs-string">"exit"</span>)) &#123;
				bufferedReader.close();
				<span class="hljs-keyword">break</span>;
			&#125;
			
			BracketChecker checker = <span class="hljs-keyword">new</span> BracketChecker(input);
			checker.chekc();
		&#125;
	&#125;

	<span class="hljs-comment">// 通过缓冲流中的'readLine'方法高效读入用户的数据.</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">getString</span><span class="hljs-params">()</span> </span>&#123;

		String s = <span class="hljs-keyword">null</span>;
		bufferedReader = <span class="hljs-keyword">new</span> BufferedReader(<span class="hljs-keyword">new</span> InputStreamReader(System.in));
		<span class="hljs-keyword">try</span> &#123;
			s = bufferedReader.readLine();
		&#125; <span class="hljs-keyword">catch</span> (IOException e) &#123;
			e.printStackTrace();
		&#125;
		<span class="hljs-keyword">return</span> s;
	&#125;
&#125;</code></pre></div></li>
<li><p><em>程序运行结果如下 :</em></p>
<div class="hljs"><pre><code class="hljs java">Please enter containing delimiters : 
&#123;[&lt;a&gt;b]c)d&#125;efg
error : ) at <span class="hljs-number">8</span>
error : &#125; at <span class="hljs-number">10</span>

Please enter containing delimiters : 
&#123;([&lt;a&gt;b]c)defg
Error : missing right delimiter.

Please enter containing delimiters : 
&#123;([&lt;a&gt;b]cd&#125;efg
error : &#125; at <span class="hljs-number">10</span>
Error : missing right delimiter.

Please enter containing delimiters : 
&#123;([&lt;a&gt;b]c)d&#125;efg
Success !

Please enter containing delimiters : 
exit</code></pre></div></li>
</ul>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/Java/">Java</a>
                    
                      <a class="hover-with-bg" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/2019/04/14/Java-annotation/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">Java annotation</span>
                        <span class="visible-mobile">Previous</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/2019/04/12/A-simple-MVC-example/">
                        <span class="hidden-mobile">A simple MVC example</span>
                        <span class="visible-mobile">Next</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;TOC</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "详解Stack的实现方式及其应用&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>







  
  
    <script>
      !function (e, t, a) {
        function r() {
          for (var e = 0; e < s.length; e++) s[e].alpha <= 0 ? (t.body.removeChild(s[e].el), s.splice(e, 1)) : (s[e].y--, s[e].scale += .004, s[e].alpha -= .013, s[e].el.style.cssText = "left:" + s[e].x + "px;top:" + s[e].y + "px;opacity:" + s[e].alpha + ";transform:scale(" + s[e].scale + "," + s[e].scale + ") rotate(45deg);background:" + s[e].color + ";z-index:99999");
          requestAnimationFrame(r)
        }

        function n() {
          var t = "function" == typeof e.onclick && e.onclick;
          e.onclick = function (e) {
            t && t(), o(e)
          }
        }

        function o(e) {
          var a = t.createElement("div");
          a.className = "heart", s.push({
            el: a,
            x: e.clientX - 5,
            y: e.clientY - 5,
            scale: 1,
            alpha: 1,
            color: c()
          }), t.body.appendChild(a)
        }

        function i(e) {
          var a = t.createElement("style");
          a.type = "text/css";
          try {
            a.appendChild(t.createTextNode(e))
          } catch (t) {
            a.styleSheet.cssText = e
          }
          t.getElementsByTagName("head")[0].appendChild(a)
        }

        function c() {
          return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
        }

        var s = [];
        e.requestAnimationFrame = e.requestAnimationFrame || e.webkitRequestAnimationFrame || e.mozRequestAnimationFrame || e.oRequestAnimationFrame || e.msRequestAnimationFrame || function (e) {
          setTimeout(e, 1e3 / 60)
        }, i(".heart{width: 10px;height: 10px;position: fixed;background: #f00;transform: rotate(45deg);-webkit-transform: rotate(45deg);-moz-transform: rotate(45deg);}.heart:after,.heart:before{content: '';width: inherit;height: inherit;background: inherit;border-radius: 50%;-webkit-border-radius: 50%;-moz-border-radius: 50%;position: fixed;}.heart:after{top: -5px;}.heart:before{left: -5px;}"), n(), r()
      }(window, document);
    </script>
  














</body>
</html>
